﻿namespace AdvancedTraining.Lesson45;

// 来自京东笔试
// 小明手中有n块积木，并且小明知道每块积木的重量。现在小明希望将这些积木堆起来
// 要求是任意一块积木如果想堆在另一块积木上面，那么要求：
// 1) 上面的积木重量不能小于下面的积木重量
// 2) 上面积木的重量减去下面积木的重量不能超过x
// 3) 每堆中最下面的积木没有重量要求
// 现在小明有一个机会，除了这n块积木，还可以获得k块任意重量的积木。
// 小明希望将积木堆在一起，同时希望积木堆的数量越少越好，你能帮他找到最好的方案么？
// 输入描述:
// 第一行三个整数n,k,x，1<=n<=200000，0<=x,k<=1000000000
// 第二行n个整数，表示积木的重量，任意整数范围都在[1,1000000000]
// 样例输出：
// 13 1 38
// 20 20 80 70 70 70 420 5 1 5 1 60 90
// 1 1 5 5 20 20 60 70 70 70 80 90 420 -> 只有1块魔法积木，x = 38
// 输出：2
// 解释：
// 两堆分别是
// 1 1 5 5 20 20 (50) 60 70 70 70 80 90
// 420
// 其中x是一个任意重量的积木，夹在20和60之间可以让积木继续往上搭
public class SplitBuildingBlock
{
    /// <summary>
    /// 这是启发解法（递归解法）
    /// arr是从小到大排序的，x是限制，固定参数
    /// 当前来到i位置，积木重量arr[i]
    /// 潜台词 : 当前i位置的积木在一个堆里，堆的开头在哪？之前已经决定了
    /// i i+1 该在一起 or 该用魔法积木弥合 or 该分家
    /// 返回值：arr[i....]最少能分几个堆？
    /// </summary>
    /// <param name="arr">积木重量数组（已排序）</param>
    /// <param name="x">相邻积木重量差的最大限制</param>
    /// <param name="i">当前位置</param>
    /// <param name="r">剩余魔法积木数量</param>
    /// <returns>最少能分几个堆</returns>
    public static int Zuo(int[] arr, int x, int i, int r)
    {
        if (i == arr.Length - 1) return 1;
        // i没到最后一个数
        if (arr[i + 1] - arr[i] <= x)
            // 一定贴在一起
            return Zuo(arr, x, i + 1, r); // 弥合！分家

        // 分家
        var p1 = 1 + Zuo(arr, x, i + 1, r);
        // 弥合
        var p2 = int.MaxValue;
        var need = (arr[i + 1] - arr[i] - 1) / x;
        if (r >= need) p2 = Zuo(arr, x, i + 1, r - need);
        return Math.Min(p1, p2);
    }

    /// <summary>
    /// 这是最优解（贪心算法）
    /// arr里装着所有积木的重量
    /// k是魔法积木的数量，每一块魔法积木都能变成任何重量
    /// x差值，后 - 前 <= x
    /// </summary>
    /// <param name="arr">积木重量数组</param>
    /// <param name="k">魔法积木数量</param>
    /// <param name="x">相邻积木重量差的最大限制</param>
    /// <returns>最少能分几个堆</returns>
    public static int MinSplit(int[] arr, int k, int x)
    {
        Array.Sort(arr);
        var n = arr.Length;
        var needs = new int[n];
        var size = 0;
        var splits = 1;
        for (var i = 1; i < n; i++)
            if (arr[i] - arr[i - 1] > x)
            {
                needs[size++] = arr[i] - arr[i - 1];
                splits++;
            }

        if (splits == 1 || x == 0 || k == 0) return splits;
        // 试图去利用魔法积木，弥合堆！
        Array.Sort(needs, 0, size);
        for (var i = 0; i < size; i++)
        {
            var need = (needs[i] - 1) / x;
            if (k >= need)
            {
                splits--;
                k -= need;
            }
            else
            {
                break;
            }
        }

        return splits;
    }

    /// <summary>
    /// 测试方法
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 积木分割问题测试 ===");

        // 测试用例1：示例案例
        Console.WriteLine("测试用例1：示例案例");
        var arr1 = new[] { 20, 20, 80, 70, 70, 70, 420, 5, 1, 5, 1, 60, 90 };
        var k1 = 1;
        var x1 = 38;
        var result1 = MinSplit((int[])arr1.Clone(), k1, x1);
        Console.WriteLine($"输入积木：[{string.Join(", ", arr1.OrderBy(a => a))}]");
        Console.WriteLine($"魔法积木数量：{k1}，最大差值：{x1}");
        Console.WriteLine($"最少堆数：{result1}");
        Console.WriteLine($"期望：2，实际：{result1}，{(result1 == 2 ? "通过" : "失败")}");
        Console.WriteLine();

        // 测试用例2：无需分割
        Console.WriteLine("测试用例2：无需分割");
        var arr2 = new[] { 1, 2, 3, 4, 5 };
        var k2 = 0;
        var x2 = 10;
        var result2 = MinSplit((int[])arr2.Clone(), k2, x2);
        Console.WriteLine($"输入积木：[{string.Join(", ", arr2)}]");
        Console.WriteLine($"魔法积木数量：{k2}，最大差值：{x2}");
        Console.WriteLine($"最少堆数：{result2}");
        Console.WriteLine($"期望：1，实际：{result2}，{(result2 == 1 ? "通过" : "失败")}");
        Console.WriteLine();

        // 测试用例3：必须分割
        Console.WriteLine("测试用例3：必须分割");
        var arr3 = new[] { 1, 100, 200, 300 };
        var k3 = 0;
        var x3 = 10;
        var result3 = MinSplit((int[])arr3.Clone(), k3, x3);
        Console.WriteLine($"输入积木：[{string.Join(", ", arr3)}]");
        Console.WriteLine($"魔法积木数量：{k3}，最大差值：{x3}");
        Console.WriteLine($"最少堆数：{result3}");
        Console.WriteLine($"期望：4，实际：{result3}，{(result3 == 4 ? "通过" : "失败")}");
        Console.WriteLine();

        // 测试用例4：有魔法积木可以弥合
        Console.WriteLine("测试用例4：有魔法积木可以弥合");
        var arr4 = new[] { 1, 15, 30 };
        var k4 = 2;
        var x4 = 10;
        var result4 = MinSplit((int[])arr4.Clone(), k4, x4);
        Console.WriteLine($"输入积木：[{string.Join(", ", arr4)}]");
        Console.WriteLine($"魔法积木数量：{k4}，最大差值：{x4}");
        Console.WriteLine($"最少堆数：{result4}");
        Console.WriteLine($"期望：1，实际：{result4}，{(result4 == 1 ? "通过" : "失败")}");
        Console.WriteLine("弥合逻辑：1到15需要(15-1-1)/10=1个魔法积木，15到30需要(30-15-1)/10=1个魔法积木");
        Console.WriteLine();

        // 测试用例5：x=0特殊情况
        Console.WriteLine("测试用例5：x=0特殊情况");
        var arr5 = new[] { 1, 1, 2, 2 };
        var k5 = 10;
        var x5 = 0;
        var result5 = MinSplit((int[])arr5.Clone(), k5, x5);
        Console.WriteLine($"输入积木：[{string.Join(", ", arr5)}]");
        Console.WriteLine($"魔法积木数量：{k5}，最大差值：{x5}");
        Console.WriteLine($"最少堆数：{result5}");
        Console.WriteLine($"期望：2，实际：{result5}，{(result5 == 2 ? "通过" : "失败")}");
        Console.WriteLine();

        // 测试用例6：单个积木
        Console.WriteLine("测试用例6：单个积木");
        var arr6 = new[] { 42 };
        var k6 = 5;
        var x6 = 100;
        var result6 = MinSplit((int[])arr6.Clone(), k6, x6);
        Console.WriteLine($"输入积木：[{string.Join(", ", arr6)}]");
        Console.WriteLine($"魔法积木数量：{k6}，最大差值：{x6}");
        Console.WriteLine($"最少堆数：{result6}");
        Console.WriteLine($"期望：1，实际：{result6}，{(result6 == 1 ? "通过" : "失败")}");
        Console.WriteLine();

        // 测试用例7：重复积木很多
        Console.WriteLine("测试用例7：重复积木很多");
        var arr7 = new[] { 1, 1, 1, 1, 1, 100, 100, 100, 100 };
        var k7 = 1;
        var x7 = 0;
        var result7 = MinSplit((int[])arr7.Clone(), k7, x7);
        Console.WriteLine($"输入积木：[{string.Join(", ", arr7)}]");
        Console.WriteLine($"魔法积木数量：{k7}，最大差值：{x7}");
        Console.WriteLine($"最少堆数：{result7}");
        Console.WriteLine($"期望：2，实际：{result7}，{(result7 == 2 ? "通过" : "失败")}");
        Console.WriteLine();

        // 测试用例8：复杂情况
        Console.WriteLine("测试用例8：复杂情况");
        var arr8 = new[] { 1, 5, 10, 20, 35, 50, 75, 100 };
        var k8 = 3;
        var x8 = 15;
        var result8 = MinSplit((int[])arr8.Clone(), k8, x8);
        Console.WriteLine($"输入积木：[{string.Join(", ", arr8)}]");
        Console.WriteLine($"魔法积木数量：{k8}，最大差值：{x8}");
        Console.WriteLine($"最少堆数：{result8}");
        Console.WriteLine("分析：弥合35到50需要(50-35-1)/15=1个魔法积木，可以完全弥合成1堆");
        Console.WriteLine($"实际：{result8}，{(result8 == 1 ? "通过" : "失败")}");
        Console.WriteLine();

        // 测试启发解法对比
        Console.WriteLine("=== 启发解法测试 ===");
        var testArr = new[] { 1, 20, 60, 90, 420 };
        var testK = 1;
        var testX = 38;
        Array.Sort(testArr);

        Console.WriteLine($"测试数组：[{string.Join(", ", testArr)}]");
        Console.WriteLine($"魔法积木：{testK}，最大差值：{testX}");

        var optimalResult = MinSplit((int[])testArr.Clone(), testK, testX);
        var heuristicResult = Zuo((int[])testArr.Clone(), testX, 0, testK);

        Console.WriteLine($"最优解结果：{optimalResult}");
        Console.WriteLine($"启发解结果：{heuristicResult}");
        Console.WriteLine($"结果一致性：{(optimalResult == heuristicResult ? "通过" : "失败")}");
    }
}